package com.cwj.lab3;

import com.cwj.lab1.LinkQueue;
import com.cwj.lab1.myArrayList;

public class BFS {
    /**
     * 广度优先搜索
     * @param start 选择的开始结点
     * 下面是传统的实现方式，原理上面有讲
     * */
    public myArrayList<Integer> BFSTaverl(Graph_matrix graph,int start){
        LinkQueue<Integer> que=new LinkQueue<>();
        myArrayList<Integer>travel=new myArrayList<>();
        que.push(start);
        boolean[]vis=new boolean[graph.getV_num()];
        while(!que.isEmpty()){
            int tt=que.pop();
            if(!vis[tt]){
                vis[tt]=true;
                travel.addLast(tt);
                for (int i = 0; i < graph.getV_num(); i++) {
                    if(vis[i])continue;
                    if(graph.getVal(tt,i)==graph.getINF()){
                        continue;
                    }
                    que.push(i);
                }
            }
        }
        return travel;
    }

}
